package test;

enum COLOR {
    RED, BLACK
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    COLOR color;

    public TreeNode(int val) {
        this.val = val;
        this.color = COLOR.RED;
    }
}

public class RBTree {
    public TreeNode root;

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            root.color = COLOR.BLACK;
            return true;
        }

        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null) {
            if (cur.val < val) {
                pre = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                pre = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }

        if (pre.val < val) {
            pre.right = node;
        } else {
            pre.left = node;
        }
        node.parent = pre;
        cur = node;

        while (pre != null && pre.color == COLOR.RED) {
            TreeNode grandFather = pre.parent;
            if (pre == grandFather.left) {
                TreeNode uncle = grandFather.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    pre.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    pre = cur.parent;
                } else {

                }
            } else {

            }
        }

        return true;
    }

    public static void main(String[] args) {
        RBTree rbTree = new RBTree();

    }
}
